Search Results

Documents authored by Ullman, Jonathan

Document
DOI: 10.4230/LIPIcs.ITCS.2024.3
Differentially Private Medians and Interior Points for Non-Pathological Data

Authors: Maryam Aliakbarpour, Rose Silver, Thomas Steinke, and Jonathan Ullman

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We construct sample-efficient differentially private estimators for the approximate-median and interior-point problems, that can be applied to arbitrary input distributions over ℝ satisfying very mild statistical assumptions. Our results stand in contrast to the surprising negative result of Bun et al. (FOCS 2015), which showed that private estimators with finite sample complexity cannot produce interior points on arbitrary distributions.
Cite as

Maryam Aliakbarpour, Rose Silver, Thomas Steinke, and Jonathan Ullman. Differentially Private Medians and Interior Points for Non-Pathological Data. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aliakbarpour_et_al:LIPIcs.ITCS.2024.3,
  author =	{Aliakbarpour, Maryam and Silver, Rose and Steinke, Thomas and Ullman, Jonathan},
  title =	{{Differentially Private Medians and Interior Points for Non-Pathological Data}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{3:1--3:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.3},
  URN =		{urn:nbn:de:0030-drops-195313},
  doi =		{10.4230/LIPIcs.ITCS.2024.3},
  annote =	{Keywords: Differential Privacy, Statistical Estimation, Approximate Medians, Interior Point Problem}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.12
Fractional Set Cover in the Streaming Model

Authors: Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We study the Fractional Set Cover problem in the streaming model. That is, we consider the relaxation of the set cover problem over a universe of n elements and a collection of m sets, where each set can be picked fractionally, with a value in [0,1]. We present a randomized (1+a)-approximation algorithm that makes p passes over the data, and uses O(polylog(m,n,1/a) (mn^(O(1/(pa)))+n)) memory space. The algorithm works in both the set arrival and the edge arrival models. To the best of our knowledge, this is the first streaming result for the fractional set cover problem. We obtain our results by employing the multiplicative weights update framework in the streaming settings.
Cite as

Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee. Fractional Set Cover in the Streaming Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{indyk_et_al:LIPIcs.APPROX-RANDOM.2017.12,
  author =	{Indyk, Piotr and Mahabadi, Sepideh and Rubinfeld, Ronitt and Ullman, Jonathan and Vakilian, Ali and Yodpinyanee, Anak},
  title =	{{Fractional Set Cover in the Streaming Model}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.12},
  URN =		{urn:nbn:de:0030-drops-75613},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.12},
  annote =	{Keywords: Streaming Algorithms, Fractional Set Cover, LP relaxation, Multiplicative Weight Update}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact